IJTCS | 大会特邀报告介绍（二）

编者按

首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2020年8月17日-21日在线上举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。  

大会简介 → 国际理论计算机联合大会重磅登场

大会特邀报告人

Silvio Micali

美国麻省理工大学教授，图灵奖得主，密码学、信息安全等领域的知名学者，区块链协议Algorand负责人

蔡进一

美国威斯康星麦迪逊大学教授，理论计算科学领域的知名学者，曾获得美国总统青年学者奖和Alfred P. Sloan Research Fellow 等荣誉

应明生

悉尼科技大学杰出教授，主要研究领域包括形式化方法、量子计算与量子信息、计算机科学与人工智能中的逻辑学、模糊逻辑等

汪  军

英国伦敦大学学院教授、阿兰·图灵研究所Turing Fellow，研究领域为多智能体强化学习、博弈论、机制设计等

孙晓明

中科院计算所研究员，主要研究领域为算法与计算复杂性、量子计算、社交网络算法等

陆品燕

上海财经大学教授，主要研究领域包括近似计数、计数问题的复杂性、算法博弈论、全息算法等

本次带来第二期大会特邀报告简介。

第一期 → 大会特邀报告介绍（一）

The Truly Distributed Blockchain

Abstract

In its ideal model, a blockchain consists of a digital ledger of unalterable data, readable by everyone, to which everyone can add new data. If adequately implemented, this model stands to revolutionize the way societies and traditional economies operate. By removing costly intermediaries and introducing new paradigms of trust, the model makes traditional transactions (e.g. payments) more efficient, and totally new ways of transacting (e.g. smart contracts) possible.

Unfortunately, as currently implemented, most blockchains cannot achieve their enormous potential. We shall argue, however, that they can be adequately implemented by means of dramatically different approaches.

Biography

Silvio Micali has been on the faculty at Electrical Engineering and Computer Science Department, MIT, the United States of America since 1983. He is the recipient of the Turing Award (in computer science), of the Gödel Prize (in theoretical computer science) and the RSA prize (in cryptography). He is a member of the National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences and Accademia dei Lincei.

Silvio's research interests include cryptography, zero knowledge, pseudorandom generation, secure protocols, mechanism design and blockchain. In particular, Silvio is the co-inventor of probabilistic encryption, Zero-Knowledge Proofs, Verifiable Random Functions and many of the protocols that are the foundations of modern cryptography. In 2017, Silvio founded Algorand, a fully decentralized, secure, and scalable blockchain which provides a common platform for building products and services for a borderless economy.

Silvio received his Laurea in Mathematics from the University of Rome, Italy, and his PhD in Computer Science from the University of California at Berkeley, the United States of America.

Some Recent Development in the Classification Program of Counting Problems

Abstract

First I will give an overview of some recent development in the complexity classification of counting problems. This is addressed in three successively more general frameworks: Graph homomorphisms (or vertex models), Counting constraint satisfaction problems (#CSP), and Holant problems. Then I will describe some complexity dichotomy theorems that classify every problem in a class into either polynomial-time computable ones, or #P-hard problems, depending on the specific constraint functions that define the problem. There are also complexity trichotomy theorems that carve out a broad class of problems that are #P-hard in general but solvable in polynomial-time on planar instances. These include Valiant's holographic reductions to Kasteleyn's algorithm for planar perfect matchings, and more. And many open problems still remain.

Biography

Jin-Yi Cai is Professor of Computer Science and Steenbock Professor of Mathematical Sciences at the University of Wisconsin - Madison, the United States of America. He received a Presidential Young Investigator Award in 1990, an Alfred P. Sloan Fellowship in Computer Science in 1994, a John Simon Guggenheim Fellowship in 1998, and a Morningside Silver Medal of Mathematics in 2004. He also received the Humboldt Research Award for Senior U.S. Scientists. He has been elected a Fellow of ACM, AAAS, and a foreign member of Academia Europaea. He is an Editor of Journal of Computer and Systems Sciences (JCSS), an Editor of International Journal of Foundations of Computer Science, an Associate Editor of Journal of Complexity, an Editor of The Chicago Journal of Theoretical Computer Science, and an Area Editor for International Journal of Software and Informatics. He works in computational complexity theory and has written and published over 100 research papers.

Jin-Yi studied at Fudan University, China (class of 77) and continued his study at Temple University and at Cornell University, the United States of America, where he received his Ph. D. in 1986. Before joining the University of Wisconsin – Madison, he held faculty positions at Yale University, the United States of America (1986-1989), Princeton University, the United States of America (1989-1993), and SUNY Buffalo, the United States of America (1993-2000), rising from Assistant Professor to Full Professor in 1996.

Some Open Problems in Decision Tree Complexity

Abstract

Decision tree is a simple but important computational model for Boolean functions. Decision tree complexity has been a widely studied subarea in computational complexity. In this talk, beside some basic concepts and models in decision tree complexity, I will mainly introduce some open problems and survey their recent progress, including the proof of sensitivity conjecture and quantum evasiveness conjecture.

Biography

Xiaoming Sun is a researcher in Institute of computing, Chinese Academy of Sciences, China. His main research fields include algorithms and computational complexity, quantum computing and social network algorithms. He has won the first batch of excellent young people's support from the National Natural Science Foundation of China (NSFC). He has been selected as the top-notch young talents in the Ten Thousand Talent Program of the Central Committee of the Communist Party of China, and has won the Outstanding Youth Award and the second prize in Cryptography Innovation in the Chinese cryptology society.

Xiaoming is the deputy director of CCF theory Committee, member of cryptology mathematics Committee and member of the Steering Committee of the International Computing and Combinatorics Conference (COCOON). He is also editorial board member of annals such as Journal of Software, Computer Research and Development, Journal of Computer Science and Technology (JCST), and young editorial board member of Science in China: Information Science.

大会主席

John Hopcroft

中国科学院外籍院士、北京大学访问讲席教授

林惠民

中国科学院院士、中国科学院软件研究所专家

大会联合主席

邓小铁

北京大学教授

顾问委员会主席

高  文

中国工程院院士、北京大学教授

梅  宏

中国科学院院士、CCF理事长

张平文

中国科学院院士、CSIAM理事长、北京大学教授

组织单位

欢迎注册

大会网站：

https://econcs.pku.edu.cn/ijtcs2020/IJTCS2020.html

注册链接：

https://econcs.pku.edu.cn/ijtcs2020/Registration.htm

联系人

大会赞助、合作等信息，请联系：[e-mail]

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转大会网站